/*
https://leetcode-cn.com/problems/elimination-game/solution/xiao-chu-you-xi-by-leetcode-solution-ydpb/
 */
public class Solution390 {
    public int lastRemaining(int n) {
        int total=n,sub=1,first=1,dir=1;
        while (total>1){
            if (dir==1 || dir==0 && total%2==1){
                first=first+sub;
            }
            total=total/2;
            sub=sub*2;
            dir=1-dir;
        }
        return first;
    }

    public static void main(String[] args) {
        System.out.println(new Solution390().lastRemaining(9));
    }
}
